#pragma once    // 防止头文件被重复包含
#include<iostream>
#include<assert.h>
using namespace std;

template<class T>
struct AVLtree_node
{
    T _val; // 权值
    int _h; // 以该节点为根的子树的高度（为了保持平衡）
    int _size;  // 以该节点为根的子树的大小（为了可以查询树中排名第k的节点）

    AVLtree_node* _left;    // 左儿子
    AVLtree_node* _right;   // 右儿子
    AVLtree_node* _parent;  // 父节点
    AVLtree_node(const T& x = T(), int cnt = 1)
        :_val(x)
        ,_h(1)
        ,_size(1)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
    {}
};

// 迭代器
template<class T>
struct AVLtree_iterator
{
    typedef AVLtree_node<T>		node;
	typedef node*				node_ptr;
    typedef AVLtree_iterator	Self;

    node_ptr _ptr;		// 封装节点的指针
    node_ptr _root;		// 为了处理--end(), 还需额外封装一个_root指向树的根节点
	// （若树中执行插入/删除，根节点可能会改变，迭代器就会失效）
    AVLtree_iterator(node_ptr p = nullptr, node_ptr r = nullptr)
        :_ptr(p)
		,_root(r)
    {}
    
	// 前置++，找后继
    Self& operator++()
    {
		// 特判迭代器为end()的情况
		if (!_ptr)	
			assert(false);

        if(_ptr->_right)
        {
            _ptr = _ptr->_right;
            while(_ptr->_left)
                _ptr = _ptr->_left;
        }
        else{
            node_ptr p = _ptr->_parent;
            while(p && _ptr == p->_right)
            {
                _ptr = p;
                p = p->_parent;
            }
            _ptr = p;
        }
        return *this;
    }
	// 后置++
	Self operator++(int)
	{
		Self tmp(*this);
		++(*this);
		return tmp;
	}

	// 前置--，找前驱
    Self& operator--()
    {
        // 特判迭代器为end()的情况
        if(!_ptr){ 
			if (!_root)		// 空树应当直接报错
				assert(false);

			// 找最后一个节点
            _ptr = _root;
            while(_ptr->_right)
                _ptr = _ptr->_right;
            return *this;
        }
        if(_ptr->_left)
        {
            _ptr = _ptr->_left;
            while(_ptr->_right)
                _ptr = _ptr->_right;
        }
        else{
            node_ptr p = _ptr->_parent;
            while(p && _ptr == p->_left)
            {
                _ptr = p;
                p = p->_parent;
            }
            _ptr = p;
        }
        return *this;
    }
	// 后置--
	Self operator--(int)
	{
		Self tmp(*this);
		--(*this);
		return tmp;
	}

    bool operator==(const Self& it) const
    { return _ptr == it._ptr; }
    bool operator!=(const Self& it) const
    { return _ptr != it._ptr; }

    T& operator* () { return _ptr->_val; }
    T* operator-> () { return &_ptr->_val; }
};

// const迭代器
template<class T>
struct AVLtree_const_iterator
{
    typedef AVLtree_node<T>			node;
	typedef const node*				node_ptr;
    typedef AVLtree_const_iterator	Self;

    node_ptr _ptr;		// 封装节点的指针
    node_ptr _root;		// 为了处理--end(), 还需额外封装一个_root指向树的根节点
    AVLtree_const_iterator(node_ptr p = nullptr, node_ptr r = nullptr)
        :_ptr(p)
		,_root(r)
    {}
	AVLtree_const_iterator(const AVLtree_iterator<T>& it) 
		:_ptr(it._ptr)
		,_root(it._root)
	{}
    
	// 前置++，找后继
    Self& operator++()
    {
		// 特判迭代器为end()的情况
		if (!_ptr)	
			assert(false);

        if(_ptr->_right)
        {
            _ptr = _ptr->_right;
            while(_ptr->_left)
                _ptr = _ptr->_left;
        }
        else{
            node_ptr p = _ptr->_parent;
            while(p && _ptr == p->_right)
            {
                _ptr = p;
                p = p->_parent;
            }
            _ptr = p;
        }
        return *this;
    }
	// 后置++
	Self operator++(int)
	{
		Self tmp(*this);
		++(*this);
		return tmp;
	}

	// 前置--，找前驱
    Self& operator--()
    {
        // 特判迭代器为end()的情况
        if(!_ptr){ 
			if (!_root)		// 空树应当直接报错
				assert(false);

			// 找最后一个节点
            _ptr = _root;
            while(_ptr->_right)
                _ptr = _ptr->_right;
            return *this;
        }
        if(_ptr->_left)
        {
            _ptr = _ptr->_left;
            while(_ptr->_right)
                _ptr = _ptr->_right;
        }
        else{
            node_ptr p = _ptr->_parent;
            while(p && _ptr == p->_left)
            {
                _ptr = p;
                p = p->_parent;
            }
            _ptr = p;
        }
        return *this;
    }
	// 后置--
	Self operator--(int)
	{
		Self tmp(*this);
		--(*this);
		return tmp;
	}

    bool operator==(const Self& it) const
    { return _ptr == it._ptr; }
    bool operator!=(const Self& it) const
    { return _ptr != it._ptr; }

    const T& operator* () { return _ptr->_val; }
    const T* operator-> () { return &_ptr->_val; }
};


template<class K, class T, class K_of_T, class Compare = less<K>>
class AVLtree
{
	typedef AVLtree_node<T> node;
protected:
	node* _root = nullptr;
public:

	AVLtree(){}
	AVLtree(initializer_list<T> il)
    {
        for(auto& e : il)
            insert(e);
    }

	// 迭代器区间构造
	template<class InputIterator>
	AVLtree(InputIterator first, InputIterator last)
	{
		while (first != last)
		{
			insert(*first);
			++first;
		}
	}
	~AVLtree() { clear(); }
	void clear()
	{
		_clear(_root);
		_root = nullptr;
	}

	AVLtree(const AVLtree& t) { _root = copy(t._root); }

	void swap(AVLtree& t) { std::swap(_root, t._root); }
	AVLtree& operator= (const AVLtree& t)
	{
		if (this != &t)
		{
			AVLtree tmp(t);
			swap(tmp);
		}
		return *this;
	}

	typedef AVLtree_iterator<T>         iterator;
	typedef AVLtree_const_iterator<T>   const_iterator;
	iterator begin()
	{
		if (!_root) return { _root, _root };
		node* cur = _root;
		while (cur->_left) cur = cur->_left;
		return { cur, _root };
	}
	iterator end() 
    { return { nullptr, _root }; }

	const_iterator begin() const
	{
		if (!_root) return { _root, _root };
		node* cur = _root;
		while (cur->_left) cur = cur->_left;
		return { cur, _root };
	}
	const_iterator end() const 
    { return { nullptr, _root }; }

	// 求树里面的元素个数
	int size() { return size(_root); }
	bool empty() { return !_root; }

    // 找到了返回值为val的迭代器，否则返回val应当插入位置的父节点的迭代器
	iterator find(const K& val)
	{
        Compare cmp;
        K_of_T get_key;

		node* cur = _root;
		node* p = nullptr;	// 记录cur的父节点
		while (cur)
		{
			p = cur;
			if (cmp(get_key(val), get_key(cur->_val)))       // val < cur->_val
				cur = cur->_left;
			else if (cmp(get_key(cur->_val), get_key(val)))  // val > cur->_val
				cur = cur->_right;
			else
				return {cur, _root};
		}
		return {p, _root};
	}

    // 返回值为val的迭代器
	iterator insert(const T& val)
	{
		if (!_root)
		{
			_root = get_node(val);
			return {_root, _root};
		}
        Compare cmp;
        K_of_T get_key;

		node* cur = find(val)._ptr;
		if(cmp(get_key(cur->_val), get_key(val)) || cmp(get_key(val), get_key(cur->_val))) // cur->_val != val
		{
			// 到这里说明未找到，cur是val应插入的位置的父节点
			node* p = cur;
			cur = get_node(val);
			cur->_parent = p;
			if (cmp(get_key(val), get_key(p->_val))) p->_left = cur;
			else p->_right = cur;
            update(cur);
		}
        return {cur, _root};
	}

    // 返回成功删除的元素个数
	int erase(const K& key)
    {
        if(!_root) return 0;
        node* cur = find(key)._ptr;
        if(!cmp(get_key(cur->_val), key) && !cmp(key, get_key(cur->_val))) // 相等
        {
            node* p = cur->_parent;
            // 1.叶子节点：直接删除
            if(!cur->_left && !cur->_right)
            {
                if(!p) _root = nullptr; // 特判只有一个节点
                else if(cur == p->_left) 
                    p->_left = nullptr;
                else 
                    p->_right = nullptr;
                del_node(cur);
                update(p);	// 删除后从父节点往上更新
            }
            // 2.只有一个儿子：用儿子替代
            else if(!cur->_left || !cur->_right)
            {
                node* child = cur->_left ? cur->_left : cur->_right;
                if(!p) _root = child;   // 特判只有一个节点
                else if(p->_left == cur) 
                    p->_left = child;
                else 
                    p->_right = child;
                child->_parent = p;		// 别忘记连接父节点
                del_node(cur);
                update(p);	// 删除后从父节点往上更新
            }
            // 3.有两个儿子: 用前驱替代，然后删除前驱
            else{
                // 找前驱
                node* pre = cur->_left;
                node* pre_parent = cur;
                while(pre->_right) 
                {
                    pre_parent = pre;
                    pre = pre->_right;
                }
                // // 交换，然后删除前驱节点
                // std::swap(cur->_val, pre->_val);
                // // 到这里pre必定没有右儿子
                // if(pre_parent->_left == pre) 
                //     pre_parent->_left = pre->_left;
                // else 
                //     pre_parent->_right = pre->_left;
                // if(pre->_left) 
                //     pre->_left->_parent = pre_parent;

                node* x = cur, *y = pre;
                node* xp = x->_parent, *xl = x->_left, *xr = x->_right;
                node* yp = y->_parent, *yl = y->_left;
                if(yp->_left == y){
                    // 该情况说明y的父节点就是x
                    y->_parent = xp;
                    if(xp){
                        if(xp->_left == x) xp->_left = y;
                        else xp->_right = y;
                    }
                    else    _root = y;
                    y->_right = xr;
                    xr->_parent = y;
                    update(y);
                }
                else{
                    // 该情况说明y的父节点不是x
                    yp->_right = yl;
                    if(yl) yl->_parent = yp;
                    y->_parent = x->_parent;
                    if(x->_parent){
                        if(x->_parent->_left == x)
                            x->_parent->_left = y;
                        else 
                            x->_parent->_right = y;
                    }
                    else _root = y;

                    y->_left = xl;
                    xl->_parent = y;
                    y->_right = xr;
                    xr->_parent = y;
                    update(yp);
                }

                del_node(x);
            }
            return 1;
        }
        return 0;
    }

protected:


	void _clear(node* x)
	{
		if (!x) return;
		_clear(x->_left);
		_clear(x->_right);
		del_node(x);
	}

	node* copy(node* x)
	{
		if (!x) return nullptr;
		node* le = copy(x->_left);
		node* ri = copy(x->_right);
		node* root = get_node(x->_val);
		root->_left = le, root->_right = ri;
		if (le) le->_parent = root;
		if (ri) ri->_parent = root;
		return root;
	}

	node* get_node(const T& val, int cnt = 1)  {  return new node(val, cnt);  }
	void del_node(node* x) { delete x; }

	int height(node* x) { return x ? x->_h : 0; }
	int size(node* x) { return x ? x->_size : 0; }

	// 更新x的_h与_size
	void push_up(node* x)
	{
		if (x)
		{
			x->_h = max(height(x->_left), height(x->_right)) + 1;
			x->_size = size(x->_left) + size(x->_right) + 1;
		}
	}
    void update(node* p)
    {
        while(p)
        {
            node* g = p->_parent;
            int l = height(p->_left), r =height(p->_right);
            if(abs(l - r) <= 1)
                push_up(p);
            else       // 平衡破坏，需旋转调整
                balance(p);
            p = g;
        }
    }
	void balance(node* p)
	{
		int l = height(p->_left), r = height(p->_right);
		if (l > r)
		{
			int ll = height(p->_left->_left), lr = height(p->_left->_right);
			if (ll >= lr)   // LL
				rotateR(p);
			else {          // LR
				rotateL(p->_left);
				rotateR(p);
			}
		}
		else {
			int rr = height(p->_right->_right), rl = height(p->_right->_left);
			if (rr >= rl)   // RR
				rotateL(p);
			else {          // RL
				rotateR(p->_right);
				rotateL(p);
			}
		}
	}
	//     g               g
	//     |               |
    //     p               x
    //    / \             / \
    //   x   C   ====>   A   p
    //  / \                 / \
    // A   B               B   C
    void rotateR(node* p)	// 右旋
    {
        node* g = p->_parent;
        node* x = p->_left;
        p->_left = x->_right;
        if(x->_right) x->_right->_parent = p;

        x->_right = p;
        p->_parent = x;

        x->_parent = g;
        if(g){
            if(p == g->_left) g->_left = x;
            else g->_right = x;
        }
		// 注意需先更新p，再更新x
        push_up(p);
        push_up(x);
        if(_root == p) // 注意可能需要更新根节点
			_root = x;
    }

	//     g               g
	//     |               |
    //     p               x
    //    / \             / \
    //   x   C   <====   A   p
    //  / \                 / \
    // A   B               B   C
    void rotateL(node* x)	// 左旋，与右旋类似
    {
        node* g = x->_parent;
        node* p = x->_right;
        x->_right = p->_left;
        if(p->_left) p->_left->_parent = x;

        p->_left = x;
        x->_parent = p;

        p->_parent = g;
        if(g){
            if(x == g->_left) g->_left = p;
            else g->_right = p;
        }
        push_up(x);
        push_up(p);
        if(_root == x) _root = p;
    }
};